package edu.dayu.demo1;

/**
 * 给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。
 * 输入：nums = [2,2,3,2]
 * 输出：3
 * 思路：其余元素都是 3 次，3次的元素 异或值 是本身 ，数组的长度为 3n+1；
 * 思路1：先排个序，然后一次计算 3个数的异或 ，值等于本身，那么就不是，不等于说明里面有一个不相同。
 */
public class 只出现一次的数字 {
    public static void main(String[] args) {
        int[] nums = {30000,500,100,30000,100,30000,100};
        System.out.println(singleNumber(nums));
    }

    public static int singleNumber(int[] nums) {
        sort(nums,0,nums.length-1);
        for (int i = 0; i < nums.length-3; i+=3) {
            if (nums[i]!=nums[i+1]||nums[i]!=nums[i+2]||nums[i+1]!=nums[i+2]){
                if (nums[i]==nums[i+1]){
                    return nums[i+2];
                }else if (nums[i]==nums[i+2]){
                    return nums[i+1];
                }else {
                    return nums[i];
                }
            }
        }
        return nums[nums.length-1];
    }

    /**
     * 快排
     * @param nums
     * @param i
     * @param j
     */
    public static void sort(int[] nums,int i,int j){
        if (i>=j){
            return;
        }
        int val = nums[i];
        int l = i;
        int r = j;
        while (l<r){
            // 从后往前找第一个小于 val 的数
            while (l<r && nums[r] > val){
                r--;
            }
            if (l < r){
                nums[l++] = nums[r];
            }
            //从前往后找第一个大于val的数字
            while (l < r && nums[l] < val){
                l ++;
            }
            if(l < r){//找到了数字
                nums[r--] = nums[l];
            }
        }
        nums[l] = val;
        sort(nums,i,l-1);
        sort(nums,l+1,j);
    }

}
